// zoj3941
// 题意：给定n(<=10)个音乐会区间，按天为单位进行。你可以选择音乐会区间的
//       任意点开始，然后从这天开始之后k(<=10^9)天都会兴奋。你可以选择
//       m(<=10^9)次开始点，相当于用m个长度为k的线段覆盖，问最后被覆盖
//       到的长度最长是多少？
//
// 题解：非常不错的贪心。先把音乐会持续区间如果有交的先合并，然后得到
//       一段段不想交的区间，然后正常来说从最左端开始，不断贪心，
//       可以放下k就放，如果这段长度到下个区间的中间点，那么就从那个中间
//       点开始放k。但是这样不一定是最优的，比如k=3, 区间为[1, 3]。
//       从1开始放了一个后把这个区间放满，但是下次不能从4开始，因为不在
//       音乐会结束时间，但是你可以从上段音乐会最后结束时间比如3再放一个
//       k，这样就可以拓展覆盖长度。
//       所以我们可以先2^n枚举每个合并后的音乐会右端点是不是要放，然后
//       正常贪心过来就好。
//
// run: $exec < input
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using pair = std::pair<long long, long long>;
std::vector<pair> v;
long long n, k, m;

void merge(std::vector<pair> & v)
{
	std::sort(v.begin(), v.end(), [](pair const & a, pair const & b) {
				return a.first < b.first || (a.first == b.first && a.second < b.second);
			});
	int n = v.size();
	for (int i = 0; i < n - 1; ) {
		if (v[i].second >= v[i + 1].first) {
			v[i].second = std::max(v[i].second, v[i + 1].second);
			n--;
			v.erase(v.begin() + i + 1);
		} else i++;
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> k >> m;
		v.clear();
		v.resize(n);
		for (int i = 0; i < n; i++)
			std::cin >> v[i].first >> v[i].second;
		merge(v);
		n = v.size();

		long long ans = 0, tm = m;
		for (int st = 0; st < (1 << n); st++) {
			long long now = 0, tans = 0; m = tm;
			for (int i = 0; i < n && m; i++) {
				now = std::max(now, v[i].first - 1);
				if (now < v[i].second) {
					long long len = v[i].second - now;
					long long t = len / k;
					t = std::min(m, t);
					now += t * k;
					tans += t * k;
					m -= t;
					if (now < v[i].second && m) {
						now += k;
						tans += k;
						m--;
					}
				}
				if ((st & (1 << i)) && m) {
					tans += std::max(0ll, v[i].second + k - 1 - now);
					now = std::max(now, v[i].second + k - 1);
					m--;
				}
			}
			ans = std::max(ans, tans);
		}
		std::cout << ans << '\n';
	}
}

